package sword.offer;

/**
 * 输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
 * 输入: [3,30,34,5,9]
 * 输出: "3033459"
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class FortyFive {
    /**
     * 这一题主要在于两个数的比较
     * 比如 3 和 30谁应该更小？ 往往我会对其中一个数进行变换后进行比较。而很少想到将两个数字结合后进行比较。
     * 其实按照题意我们只需要将这两个数进行结合比较 330（x + y） > 303(y + x) 显然，x要放在y的后面，总体上才会更小
     * 我们使用一个快排来对这些数字进行排序
     * */
    class Solution {
        public String minNumber(int[] nums) {
            String[] strs = new String[nums.length];
            for (int i = 0; i < nums.length; i++) {
                strs[i] = String.valueOf(nums[i]);
            }
            quickSort(strs, 0, nums.length-1);
            StringBuilder sb = new StringBuilder();
            for(String s : strs)
                sb.append(s);
            return sb.toString();
        }

        void quickSort(String[] strs, int l, int r){
            if(l >= r) return;
            int i=l, j=r;
            String temp = strs[l];
            while(i < j){
                while(i < j && (strs[j]+strs[l]).compareTo(strs[l]+strs[j]) >= 0){j--;}
                while(i < j && (strs[i]+strs[l]).compareTo(strs[l]+strs[i]) <= 0){i++;}
                temp = strs[i];
                strs[i] = strs[j];
                strs[j] = temp;
            }
            strs[i] = strs[l];
            strs[l] = temp;
            quickSort(strs, i+1, r);
            quickSort(strs,l, i-1);
        }
    }
}
